package _18_剑指OfferII;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class _065_剑指OfferII最短的单词编码 {

    public static void main(String[] args) {
        _065_剑指OfferII最短的单词编码 v = new _065_剑指OfferII最短的单词编码();

        String[] str = {"time", "me", "bell"};
        System.out.println(v.minimumLengthEncoding(str));
    }

    Node first = new Node();

    {
        first.children = new Node[26];
    }
    public int minimumLengthEncoding(String[] words) {
        Set<String> set = new HashSet<>(Arrays.asList(words));
        
        return 0;
    }

    public int minimumLengthEncoding1(String[] words) {
        int total = 0;
        for (String word : words) {
            int remainCount = prefix(word);
            if (remainCount == -1) {
                total += word.length() + 1;
                insert(word);
            } else if (remainCount != 0) {
                total += remainCount;
                insert(word);
            }
        }
        return total;
    }

    public void insert(String word) {
        Node node = first;
        // 逆序存储
        int len = word.length();
        for (int i = len - 1; i >= 0; --i) {
            char cur = word.charAt(i);
            Node[] children = node.children;
            if (children == null) children = node.children = new Node[26];
            Node child = children[cur - 'a'];
            if (child != null) {
                node = child;
                continue;
            }
            Node newNode = new Node();
            // 新建
            children[cur - 'a'] = newNode;
            node = newNode;
        }
    }

    // -1匹配失败，0表示全部字符插入成功，other表示还剩多少字符没有插入
    public int prefix(String prefix) {
        Node node = first;
        // 逆序存储
        int len = prefix.length();
        for (int i = len - 1; i >= 0; --i) {
            char cur = prefix.charAt(i);
            Node[] children = node.children;
            if (children == null) return len;
            Node child = children[cur - 'a'];
            if (child != null) {
                len--;
                node = child;
                continue;
            }
            return -1;
        }
        return 0;
    }

    static class Node {

        Node[] children;

    }
}
